To accurately represent a color image using digital electronics, the image is quantized to discrete locations and colors. Typically, the image is divided into a two-dimensional grid of uniformly shaped boxes, and each box is assigned a single color. This allows a computer system to represent a color image internally as a two-dimensional array of digital color values. Images represented in this manner are known as bitmapped images. A typical color imaging standard currently in use (the VGA standard), represents a color image with a 640.times.480 array of 4-bit color values. Such an array of color values can be easily stored by the computer system in a memory device. Also with this form of color image representation, the computer system can easily reproduce the stored image using a color monitor or printer with an array of colored dots (commonly referred to as pixels).
In a typical computer system, color is quantized according to the red-green-blue (RGB) color model. According to the RGB model, colors are specified by an ordered triple of values corresponding to the intensities of red, green, and blue light that are mixed to form the color. (Red, green and blue light are considered to be additive primaries.) Each of the intensity values varies from zero to one, with a one indicating full intensity of the color. For example, the ordered triple, (1,0,1), refers to the color magenta formed by the mixture of full intensity red with full intensity blue. The RGB color model is directly applicable to color monitors wherein an electron gun is used to excite red, green and blue phosphors on a screen to varying intensities. The range of colors that are displayable on such a device is known as the color gamut of the device. Other color quantization models are also commonly used and may be more suitable to some applications. However, in general, all color models use a three dimensional representation of the color gamut.
At times, colors are specified even more abstractly in a computer system using a single number or color value instead of an ordered triple in order to minimize the space required to store an image. Usually, the computer system maintains a look-up table to associate these color values with their corresponding RGB (or other color model) ordered triple. The colors in the table make up a set of colors that can be simultaneously used in a single image. The set of colors that can be simultaneously used in an image is known as the color palette.
The perceived quality of the digitized color image when reproduced depends upon its spatial and color resolutions. The spatial resolution of an image is related to the number and size of the boxes (or pixels when reproduced) into which the image is divided (and hence related to the size of the array used to represent the image). The color resolution of an image is related to the number of discrete colors that can be simultaneously used in the image (i.e., the size of the color palette). The greater the spatial and color resolutions of an image, the better its quality. For example, an image displayed with a spatial resolution of 1024.times.768 pixels is of perceptibly higher quality than the same sized image displayed with a spatial resolution of 640.times.480 pixels. Also, when displayed, an image where each color is represented by an 8-bit value (allowing the use of up to 256 different colors in the same image) is of perceptibly higher quality than an image where each color is represented by a 4-bit value (16 different simultaneous colors) .
Current high end computer systems represent color images with 24-bit color values (16.8 million colors) and provide a spatial resolution of 1280.times.1024 or higher. Systems with 24-bit color resolution are considered to be "true color" systems since the color at any pixel in the digitized image is specified with adequate color resolution to be indistinguishable from its actual color in the original image. These systems are therefore capable of reproducing images with astonishing tonal accuracy and crispness.
There are situations, however, when it is desirable to reproduce an image that has been digitized at a certain color resolution (24-bit true color, for example) using a lower color resolution. For example, it may be desirable to display with pre-existing VGA or super VGA standard hardware a color image digitized at a higher color resolution. It may also be desirable to design less expensive hardware than that required for 24-bit color resolution while providing a similar image quality. This problem can be restated generally as that of achieving the best quality color image with a limited color resolution.
In the prior art, two different approaches have been taken to solving the problem of optimizing the quality of a high resolution image reproduced at a low color resolution. The first approach involves optimally choosing the set of colors for the color palette. In typical computer systems, the color palette is user selectable, not fixed. Thus, in a VGA standard (4-bit color resolution) system, some or all of the palette of 16 colors can be designated by the user. The quality of a reproduced image can be greatly enhanced by properly selecting the optimal color palette.
Some prior art systems use adaptive techniques aimed at choosing colors for a palette that are optimal for the particular image being reproduced. One such technique is known as the popularity algorithm. This technique chooses as colors for a palette, those colors which occur most frequently in the image being reproduced. For example, for 8-bit color resolution reproductions, the 256 colors used most frequently in the image are chosen to fill the color palette. Then, when the image is reproduced, each color in the image is mapped to the nearest color in the palette. Usually, the quality of the resulting image is greatly enhanced since the actual colors of most of the image's pixels will be in the palette.
Such adaptive palette techniques, however, produce undesirable effects in a windowing environment in which several images may be simultaneously displayed. Adapting the color palette to an individual image on the display typically degrades the quality of the remaining images. Also, when the focus of the windowing environment is subsequently changed to another individual image on the display, the color palette must be re-adapted to that image. Consequently, the quality of the image to which the color palette was previously adapted becomes degraded. This undesirable effect is known as a palette war.
A second approach relies on the eye's ability to blend the colors of adjacent pixels so that an intermediate color is perceived. This approach focuses on how the pixel colors are mapped to colors in the palette to best approximate the pixel color when viewed by the human eye. (The process of mapping pixel colors to palette colors is also referred to herein as "rendering" a pixel color.)
In a standard mapping of pixel colors to palette colors, the pixel colors are simply mapped to the nearest palette color. (The nearness of two colors is determined by the distance separating the colors in the RGB or other color model.) The result is that all pixels in an area of uniform color are mapped to the same palette color. Although the pixel color is mapped to the nearest palette color, there may be a significant difference or error between the pixel color and the mapped palette color. This difference can often be readily perceptible to a viewer.
Better results can be obtained with mapping techniques that alternately map a pixel color to two or more of the nearest palette colors such that the average error between the pixel color and the palette colors is zero. When pixels are mapped in this fashion, the eye blends or averages the palette colors of several neighboring rendered pixels in the reproduced image to perceive an approximation of the original pixel colors. Two techniques that use this approach are ordered dithering and error diffusion. These techniques are both generally referred to as dithering processes.
With the ordered dithering technique, a uniform grid of colors is used as a palette (i.e. the colors of the palette are uniformly spaced in each of the red, green and blue dimensions). A pixel's color is mapped by adding an amount of dither to each dimension of the color's corresponding RGB ordered triple and then truncating the result to a palette color. The amount of dither added is dependent on the position (in cartesian coordinates) of the pixel in the image. The pixel's cartesian coordinate is used to locate a scaling factor in a square (n.times.n) threshold matrix. For a pixel with the cartesian coordinate (x,y) the scaling factor located at the position (x mod n, y mod n) in the threshold matrix is used. To determine the amount of dither added in each dimension of the color model, the scaling factor is multiplied by the spacing between palette colors in that dimension. By determining the amount of dither with a threshold matrix rather than randomly, the amount of dither varies in a recurring pattern across the image. This produces an appearance of uniform color in those areas of an image originally uniformly colored. The following is a typical threshold matrix. ##EQU1##
With error diffusion, the color of each pixel is not mapped independently of its neighboring pixels to palette colors. When error diffusing, the color of the pixels in the image are mapped one-by-one straightforwardly to the nearest palette color. However, as each pixel is mapped, the error (or directed distance in the color model) between the actual pixel color and the palette color to which it is mapped is calculated. This error is diffused to those neighboring pixels which have not yet been mapped. A common method for diffusing the error is known as the Floyd-Steinberg filter, represented by the following matrix (which assumes the pixels are mapped from left to right and top to bottom). ##EQU2##
According to the Floyd-Steinberg filter, 7/16 of the error is added to the pixel to the right of the pixel being mapped, 5/16 to the pixel below, 3/16 to the pixel below and left, and 1/16 to the pixel below and right. Other commonly used error diffusion filters include the Stucki filter and the Burkes filter.
One problem with both the ordered dithering and error diffusion techniques is that discernable artifacts are often produced in the image. Thus, while the standard ordered dithering and error diffusion techniques serve to improve the color quality of the image, the resulting image is generally flawed. The object of the present invention therefore is to reproduce color images using a lower color resolution while maintaining a high color quality. A further object is to reproduce color images with minimal artifacts.